package _06_deque.my_implements;

import _06_deque.Deque;

/**
 * @author: mornd
 * @dateTime: 2023/6/7 - 18:21
 * 使用双向环形链表实现双端队列(推荐)
 */
public class LinkedListDeque2<E> implements Deque<E> {

    /**
     * 环形链表，头尾用一个哨兵代表
     */
    Node<E> sentinel = new Node<>(null);

    int capacity;
    int size;

    public LinkedListDeque2(int capacity) {
        this.capacity = capacity;
        sentinel.prev = sentinel.next = sentinel;
    }

    @Override
    public boolean offerFirst(E e) {
        if (isFull()) {
            return false;
        }
        // s 2 1
        Node<E> a = sentinel;
        Node<E> b = sentinel.next;
        Node<E> n = new Node<>(e, a, b);
        a.next = n;
        b.prev = n;

        size++;
        return true;
    }

    @Override
    public boolean offerLast(E e) {
        if (isFull()) {
            return false;
        }
        // s 1 2
        Node<E> a = sentinel.prev;
        Node<E> b = sentinel;
        Node<E> n = new Node<>(e, a, b);
        a.next = n;
        b.prev = n;
        size++;
        return true;
    }

    // s 2  1
    @Override
    public E popFirst() {
        if (isEmpty()) {
            return null;
        }
        /*
            a removed b
            将 removed 代入到链表最后位置，
            再依次得到 a，removed，b 对象，然后进行操作

         */
        Node<E> first = sentinel.next;
        sentinel.next = first.next;
        first.next.prev = sentinel;
        size--;
        return first.item;
    }

    @Override
    public E popLast() {
        if(isEmpty()) {
            return null;
        }
        // s 1 2
        Node<E> last = sentinel.prev;
        sentinel.prev = last.prev;
        last.prev.next = sentinel;
        size--;
        return last.item;
    }

    @Override
    public E peekFirst() {
        if(isEmpty()) {
            return null;
        }
        return sentinel.next.item;
    }

    @Override
    public E peekLast() {
        if(isEmpty()) {
            return null;
        }
        return sentinel.prev.item;
    }

    @Override
    public boolean isEmpty() {
        return sentinel.next == sentinel;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    /**
     * 扩张了prev，实现双向节点
     *
     * @param <E>
     */
    static class Node<E> {
        E item;
        Node<E> prev;
        Node<E> next;

        Node(E item) {
            this.item = item;
        }

        public Node(E item, Node<E> prev, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }
}
